凸优化（一）：凸函数判定方法的证明

刚刚起步学习凸优化的过程实在伴随着种种CH3(CH2)6COOH\rm CH_3(CH_2)_6COOHCH3​(CH2​)6​COOH。在笔记之余，也写写自己对一些小问题的证明思路和从教材上受到的启发。这些东西整理成笔记有些麻烦，又不想忘掉，就发在博客上吧。

ps：CH3(CH2)6COOH\rm CH_3(CH_2)_6COOHCH3​(CH2​)6​COOH是啥，各位上过高中的同学自行理解应该没问题。有问题的百度一下:P

给定凸集C∈RnC\in\R^nC∈Rn，若函数f:C→Rf:C\rarr\Rf:C→R满足

(∀x∈C∀y∈C)(∀λ∈[0,1])(f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y))(\forall x\in C\forall y\in C)(\forall\lambda\in[0,1])(f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y)) (∀x∈C∀y∈C)(∀λ∈[0,1])(f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y))

则称fff是凸函数。

或者说，凸组合的函数值要不大于函数值的凸组合。低维的情况反应在图像上，就是y=f(x)y=f(x)y=f(x)对应图形必定在两点连线下方。

一阶判定：若函数fff是可微的，则fff是凸函数当且仅当

f(y)≥f(x)+∇Tf(x)(y−x)f(y)\geq f(x)+\nabla^Tf(x)(y-x) f(y)≥f(x)+∇Tf(x)(y−x)

即函数值大于等于其一阶逼近。

这个问题的证明在高维（f:Rn→Rf:\R^n\rarr\Rf:Rn→R）的情况下比较困难，但是在一维情况下相对简单。[1]

此时一阶判定退化为

f is convex⇔(∀x,y∈D(f))(f(y)≥f(x)+f′(x)(y−x))f\text{ is convex}\Leftrightarrow(\forall x,y\in\mathscr{D}(f))(f(y)\geq f(x)+f'(x)(y-x)) f is convex⇔(∀x,y∈D(f))(f(y)≥f(x)+f′(x)(y−x))

（原书中用domf\mathrm{dom}fdomf表示fff的前域domain of fff，我交的离散数学教材上用的是D(f)\mathscr{D}(f)D(f)，意思一致）

必要性证明： 假设fff是凸函数，由凸函数定义可得

f(x+λ(y−x))≤(1−λ)f(x)+λf(y)f(x+\lambda(y-x))\leq(1-\lambda)f(x)+\lambda f(y) f(x+λ(y−x))≤(1−λ)f(x)+λf(y)

限制λ>0\lambda>0λ>0，就可以将上述不等式变形为

f(y)≥f(x)+f(x+λ(y−x))−f(x)λf(y)\geq f(x)+\frac{f(x+\lambda(y-x))-f(x)}{\lambda} f(y)≥f(x)+λf(x+λ(y−x))−f(x)​

再变形一下，

f(y)≥f(x)+f(x+λ(y−x))−f(x)λ(y−x)⋅(y−x)f(y)\geq f(x)+\frac{f(x+\lambda(y-x))-f(x)}{\lambda(y-x)}\cdot(y-x) f(y)≥f(x)+λ(y−x)f(x+λ(y−x))−f(x)​⋅(y−x)

两边取极限t→0+t\rarr 0_+t→0+​，得

f(y)≥f(x)+f′(x)(y−x)f(y)\geq f(x)+f'(x)(y-x) f(y)≥f(x)+f′(x)(y−x)

充分性证明： 若一阶判定f(y)≥f(x)+f′(x)(y−x)f(y)\geq f(x)+f'(x)(y-x)f(y)≥f(x)+f′(x)(y−x)成立，令z=λx+(1−λ)y  (0≤λ≤1)z=\lambda x+(1-\lambda)y\;(0\leq\lambda\leq 1)z=λx+(1−λ)y(0≤λ≤1)，则可以得到

f(x)≥f(z)+f′(z)(x−z)(1)f(x)\geq f(z)+f'(z)(x-z)\tag{1} f(x)≥f(z)+f′(z)(x−z)(1)

f(y)≥f(z)+f′(z)(y−z)(2)f(y)\geq f(z)+f'(z)(y-z)\tag{2} f(y)≥f(z)+f′(z)(y−z)(2)

(1)⋅λ+(2)⋅(1−λ)(1)\cdot\lambda+(2)\cdot(1-\lambda)(1)⋅λ+(2)⋅(1−λ)，可得

λf(x)+(1−λ)f(y)≥f(z)=f(λx+(1−λ)y)\lambda f(x)+(1-\lambda)f(y)\geq f(z)=f(\lambda x+(1-\lambda)y) λf(x)+(1−λ)f(y)≥f(z)=f(λx+(1−λ)y)

这就证明了一阶判定条件（一维情况）。

证明高维情况时非常希望能够类比一维情况，但是一维的必要性证明中，使用了R\RR上函数的导数定义——Rn\R^nRn上函数的导数要用ℓ2\ell_2ℓ2​范数来定义，这是搬不过来的！

怎么解决呢？这里原书中用了一种非常精彩的证明思路：（也许是我见识短浅啦，至少我看起来是很漂亮的）

Consider fff restricted to the line passing through them(xxx and yyy)

定义g(t)=f(x+t(y−x))g(t)=f(x+t(y-x))g(t)=f(x+t(y−x))作为辅助，这个函数的导数是

g′(t)=∇f(x+t(y−x))T(y−x)g'(t)=\nabla f(x+t(y-x))^T(y-x) g′(t)=∇f(x+t(y−x))T(y−x)

然后利用这个函数来证明：

必要性证明： 假设fff是凸函数，那么

g(λt+(1−λ)s)=f(x+(λt+(1−λ)s)(y−x))=f(λ(x+t(y−x))+(1−λ)(x+s(y−x)))≥λf(x+t(y−x))+(1−λ)f(x+s(y−x))=λg(t)+(1−λ)g(s)\begin{aligned} &g(\lambda t+(1-\lambda)s) \\ =&f(x+(\lambda t+(1-\lambda)s)(y-x)) \\ =&f(\lambda(x+t(y-x))+(1-\lambda)(x+s(y-x))) \\ \geq &\lambda f(x+t(y-x))+(1-\lambda)f(x+s(y-x)) \\ =&\lambda g(t)+(1-\lambda)g(s) \end{aligned}==≥=​g(λt+(1−λ)s)f(x+(λt+(1−λ)s)(y−x))f(λ(x+t(y−x))+(1−λ)(x+s(y−x)))λf(x+t(y−x))+(1−λ)f(x+s(y−x))λg(t)+(1−λ)g(s)​

这意味着ggg也是凸函数（其实g is convexg\text{ is convex}g is convex是f is convexf\text{ is convex}f is convex的充要条件[2]，下面会证明）

虽然我拿fff没办法，但ggg是一元函数啊！根据上面已经证明的结论，g(1)≥g(0)+g′(0)⋅1g(1)\geq g(0)+g'(0)\cdot 1g(1)≥g(0)+g′(0)⋅1，回带到fff中，立即得到

f(y)≥f(x)+∇Tf(x)(y−x)f(y)\geq f(x)+\nabla^Tf(x)(y-x) f(y)≥f(x)+∇Tf(x)(y−x)

充分性证明： 若一阶判定条件成立，则有

f(x+t(y−x))≥f(x+s(y−x))+∇f(x+s(y−x))T(y−x)(t−s)f(x+t(y-x))\geq f(x+s(y-x))+\nabla f(x+s(y-x))^T(y-x)(t-s) f(x+t(y−x))≥f(x+s(y−x))+∇f(x+s(y−x))T(y−x)(t−s)

带入到ggg中，得到ggg是凸函数，这就回到了一元的情况.用两次结论可得

g(t)≥g(0)+g′(0)t(1)g(t)\geq g(0)+g'(0)t\tag{1} g(t)≥g(0)+g′(0)t(1)

g(t)≥g(1)+g′(1)(t−1)(2)g(t)\geq g(1)+g'(1)(t-1)\tag{2} g(t)≥g(1)+g′(1)(t−1)(2)

(1)⋅(1−t)+(2)⋅t(1)\cdot(1-t)+(2)\cdot t(1)⋅(1−t)+(2)⋅t，回代到fff中可得

f(x+t(y−x))≥(1−t)f(x)+tf(y)f(x+t(y-x))\geq(1-t)f(x)+tf(y) f(x+t(y−x))≥(1−t)f(x)+tf(y)

这就证明了fff是凸函数.

上面的证明主要来自Convex Optimization，我作了一点改动。

最重要的思路是

二阶判定：若函数fff是二阶可微的，则 fff是凸函数  ⟺  (∀x∈C)(∇2f(x)∈S+n)\iff(\forall x\in C)(\nabla^2f(x)\in S_+^n)⟺(∀x∈C)(∇2f(x)∈S+n​)（对称半正定）

这个问题与对称性其实无关（二阶可微保证了偏导数与求导顺序无关，那么Hessian矩阵一定是对称的），问题在于证明它是半正定的。

必要性比较容易证明，主要是通过Taylor展开来引入Hessian矩阵对应的二次型：

若fff是凸函数，则∀d∈Rn\forall d\in\R^n∀d∈Rn，f(x+td)≥f(x)+∇f(x)T(td)f(x+td)\geq f(x)+\nabla f(x)^T(td)f(x+td)≥f(x)+∇f(x)T(td).

对fff在xxx处作二阶Taylor展开得到带Peano余项的近似为

f(x+td)=f(x)+∇f(x)T(td)+12(td)T∇2f(x)(td)+o(∥td∥2)f(x+td)=f(x)+\nabla f(x)^T(td)+\frac{1}{2}(td)^T\nabla^2f(x)(td)+o(\|td\|^2) f(x+td)=f(x)+∇f(x)T(td)+21​(td)T∇2f(x)(td)+o(∥td∥2)

然后用展开式替换一阶判定左边的f(x+td)f(x+td)f(x+td)，尝试证明对于任意的向量ddd，都有dT∇2f(x)d≥0d^T\nabla^2f(x)d\geq 0dT∇2f(x)d≥0

f(x)+∇f(x)T(td)+12(td)T∇2f(x)(td)+o(∥td∥2)≥f(x)+∇f(x)T(td)⇒12(td)T∇2f(x)(td)+o(∥td∥2)≥0⇒12dT∇2f(x)d+o(∥td∥2)t2≥0⇒lim⁡t→0(12dT∇2f(x)d+o(∥td∥2)t2)≥0⇒dT∇2f(x)d≥0⇒∇2f(x)∈S+n\begin{aligned} &f(x)+\nabla f(x)^T(td)+\frac{1}{2}(td)^T\nabla^2f(x)(td)+o(\|td\|^2)\geq f(x)+\nabla f(x)^T(td) \\ \Rightarrow &\frac{1}{2}(td)^T\nabla^2f(x)(td)+o(\|td\|^2)\geq 0 \\ \Rightarrow &\frac{1}{2}d^T\nabla^2f(x)d+\frac{o(\|td\|^2)}{t^2}\geq 0 \\ \Rightarrow &\lim_{t\rightarrow 0}\Big(\frac{1}{2}d^T\nabla^2f(x)d+\frac{o(\|td\|^2)}{t^2}\Big)\geq 0 \\ \Rightarrow &d^T\nabla^2f(x)d\geq 0 \\ \Rightarrow &\nabla^2f(x)\in S_+^n \end{aligned}⇒⇒⇒⇒⇒​f(x)+∇f(x)T(td)+21​(td)T∇2f(x)(td)+o(∥td∥2)≥f(x)+∇f(x)T(td)21​(td)T∇2f(x)(td)+o(∥td∥2)≥021​dT∇2f(x)d+t2o(∥td∥2)​≥0t→0lim​(21​dT∇2f(x)d+t2o(∥td∥2)​)≥0dT∇2f(x)d≥0∇2f(x)∈S+n​​

（大概也可以通过g(t)g(t)g(t)证明，但是直接用Taylor展开更简短）

充分性我是通过构造辅助函数证明的：

首先，对于一维情况f:C⊆R→Rf:C\subseteq\R\rightarrow\Rf:C⊆R→R，Hessian矩阵退化为二阶导数.

若f′′(x)≥0f''(x)\geq 0f′′(x)≥0恒成立，则对任意的x1